package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;

/**
 * @author tzp
 * @since 2020/9/22
 */
public class LC474 implements DynamicProblem {
    int[][][] dp;
    String[] strs;

    public int findMaxForm(String[] strs, int m/*0*/, int n) {
        if (strs == null || strs.length == 0) return 0;
        this.dp = new int[m + 1][n + 1][strs.length];
        for (int i = 0; i <= m; i++) {
            for (int j = 0; j <= n; j++) {
                Arrays.fill(dp[i][j], -1);
            }
        }
        this.strs = strs;
        return rec(m, n, 0);
    }

    public int rec(int m, int n, int start) {
        if (start >= strs.length) return 0;
        if (dp[m][n][start] != -1) return dp[m][n][start];

        int maxForm = 0;
        int need0 = numOfZ(strs[start]);
        int need1 = strs[start].length() - need0;
        if (m >= need0 && n >= need1) {////拼自己
            maxForm = Math.max(maxForm, 1 + rec(m - need0, n - need1, start + 1));
        }
        maxForm = Math.max(maxForm, rec(m, n, start + 1));
        dp[m][n][start] = maxForm;
        return maxForm;
    }

    public int numOfZ(String s) {
        int sum = 0;
        for (int i = 0; i < s.length(); i++) {
            sum += s.charAt(i) == '0' ? 1 : 0;
        }
        return sum;
    }

    public static void main(String[] args) {
        System.out.println(new LC474().findMaxForm(new String[]{"10", "0001", "111001", "1", "0"}, 5, 3));
    }
}
